home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group03a.txt / 000018_icon-group-sender_Thu Feb 20 13:16:39 2003.msg < prev    next >
Internet Message Format  |  2003-12-22  |  5KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.11.1/8.11.1) id h1KKCIg23624
  4.     for icon-group-addresses; Thu, 20 Feb 2003 13:12:18 -0700 (MST)
  5. Message-Id: <200302202012.h1KKCIg23624@baskerville.CS.Arizona.EDU>
  6. From: "Frank J. Lhota" <NOSPAM.lhota.adarose@verizon.net>
  7. X-Newsgroups: comp.lang.icon
  8. Subject: Simplifying Integer Arithmetic
  9. X-Priority: 3
  10. X-MSMail-Priority: Normal
  11. X-Newsreader: Microsoft Outlook Express 6.00.2800.1106
  12. X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106
  13. Date: Thu, 20 Feb 2003 15:50:57 GMT
  14. X-Complaints-To: abuse@verizon.net
  15. To: icon-group@cs.arizona.edu
  16. Errors-To: icon-group-errors@cs.arizona.edu
  17. Status: RO
  18.  
  19. For the most part, basic integer arithmetic is quite straightforward. There
  20. is, however, one non-trivial issue in this area: when integer division does
  21. not produce an integer, how do we round the result? For example
  22.  
  23.     5 / (-3)
  24.  
  25. is between -2 and -1. Do we round 5 / (-3) to -2 or to -1?
  26.  
  27. Note that the integer "%" operator depends on how this rounding is done,
  28. since there is a requirement that in the absence of arithmetic errors, we
  29. should have
  30.  
  31.     a = b * ( a / b ) + a % b
  32.  
  33. for integers a and b.
  34.  
  35. One method of rounding is to round towards minus infinity, that is, whenever
  36. an integer division result is not an integer, round to the next smallest
  37. integer. With the "round towards minus infinity" approach, we would have the
  38. following results:
  39.  
  40.       5  /   3  =  1  &    5  %   3  =  2
  41.     (-5) /   3  = -2  &  (-5) %   3  =  1
  42.       5  / (-3) = -2  &    5  % (-3) = -1
  43.     (-5) / (-3) =  1  &  (-5) % (-3) = -2
  44.  
  45. Another method of rounding to round towards 0, that is, always round a
  46. non-integer division result to the nearest integer that has a smaller
  47. absolute value. With the "round towards 0" approach, we would have
  48.  
  49.       5  /   3  =  1  &    5  %   3  =  2
  50.     (-5) /   3  = -1  &  (-5) %   3  = -2
  51.       5  / (-3) = -1  &    5  % (-3) =  2
  52.     (-5) / (-3) =  1  &  (-5) % (-3) = -2
  53.  
  54. C, as defined by K&R, can use either the "round towards minus infinity" or
  55. the "round towards 0" method for integer division. The first ANSI standard
  56. also does not specify the rounding method to be used for integer division.
  57. Throughout the 80's and 90's, C programmers were warned that the rounding
  58. method used for integer division and remainders were platform specific.
  59.  
  60. Icon used to equally imprecise about how round is done for the "/" and "%".
  61. Originally, the rounding method used for Icon was the same as the C compiler
  62. used to implement it. This was reasonably acceptable until large integers
  63. were added. The large integer routines for division and modulus always round
  64. towards 0, irrespective of how the C compiler handles its integers. For a
  65. brief time, the rounding method used for Icon integer "/" and "%" operations
  66. depended both on the platform and on whether the integers were large
  67. integers. This was clearly unacceptable.
  68.  
  69. The Icon source file "runtime/rmisc.r" contains functions used for
  70. performing integer arithmetic with overflow checking. As part of a general
  71. fix of the Icon overflow check facilities, the overflow check functions for
  72. integer "/" and "%" operations were modified so that they always rounded to
  73. 0, irrespective of  C compiler rounding method. With this change, Icon
  74. always rounds to 0 for all integer arithmetic on all platforms.
  75.  
  76. Since this work was done, however, the C99 standard has come out. This
  77. standard finally mandates how C compilers must perform integer division and
  78. modulus operations. A C99 compliant compiler must round towards 0 when
  79. evaluating a / b for integer a and b. I know of no currently used C compiler
  80. that does not round towards 0 for these operations.
  81.  
  82. The question I pose to this group is whether we should assume that any C
  83. compiler used for Icon uses the "round towards 0" method for evaluating a /
  84. b and a % b for integers a and b. Given this assumption, we could simplify
  85. the div3 and mod3 functions in "runtime/rmisc.r" as follows:
  86.  
  87. /*
  88.  * mod3 - integer modulo with overflow checking (always rounds to 0)
  89.  */
  90. word mod3(a, b)
  91. word a, b;
  92. {
  93.    word retval;
  94.  
  95.    switch ( b )
  96.    {
  97.       case 0:
  98.   over_flow = 1; /* Not really an overflow, but definitely an error */
  99.   return 0;
  100.  
  101.       case -1:
  102.   /* Handle this separately, since -MinLong%-1 can overflow */
  103.   retval = 0;
  104.   break;
  105.  
  106.       default:
  107.   retval = a % b;
  108.   break;
  109.       }
  110.  
  111.    over_flow = 0;
  112.    return retval;
  113. }
  114.  
  115. /*
  116.  * div3 - integer divide with overflow checking (always rounds to 0)
  117.  */
  118. word div3(a, b)
  119. word a, b;
  120. {
  121.    if ( ( b == 0 ) || /* Not really an overflow, but definitely an error */
  122.         ( b == -1 && a == MinLong ) ) {
  123.       over_flow = 1;
  124.       return 0;
  125.       }
  126.  
  127.    over_flow = 0;
  128.    return a / b;
  129. }
  130.  
  131.  
  132.